package mo.byte_school;

import java.util.Arrays;
import java.util.Random;

public class L912 {

    private Random random = new Random();

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivot = random.nextInt(right-left+1) + left;
            swap(nums, pivot, right);
            int q = left - 1;
            for (int i = left; i < right; i++) {
                if (nums[i] <= nums[right]) {
                    swap(nums, i, ++q);
                }
            }
            q++;
            swap(nums, q, right);
            quickSort(nums, left, q-1);
            quickSort(nums, q+1, right);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        L912 test = new L912();
        System.out.println(Arrays.toString(test.sortArray(new int[]{5, 1, 1, 2, 0, 0})));
    }

}
